# !/usr/bin/python
# -*- coding: utf-8 -*-

"""
@contact: 微信 1257309054
@file: heap.py
@time: 2022/7/25 21:41
@author: LDC
"""
'''
9、堆排序
是采用二叉堆的数据结构来实现的。

二叉堆具有以下性质：
父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
每个节点的左右子树都是一个二叉堆（都是最大堆或最小堆）。
步骤：

构造最大堆（Build_Max_Heap）：若数组下标范围为0~n，考虑到单独一个元素是大根堆，则从下标n/2开始的元素为大根堆。于是只要从n/2-1开始，向前依次构造大根堆，这样就能保证，构造到某个节点时，它的左右子树都已经是大根堆。

堆排序（HeapSort）：由于堆是用数组模拟的。得到一个大根堆后，数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点，并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换，再对heap[0…n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换，再对heap[0…n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间，故操作完后整个数组就是有序的了。

最大堆调整（Max_Heapify）：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点 。
'''
import random
import time


def heapSort(list1):
    n = len(list1)
    first = n // 2 - 1
    for start in range(first, -1, -1):  # 构造大根堆
        maxHeapify(list1, start, n - 1)
    for end in range(n - 1, 0, -1):  # 堆排，将大根堆转换成有序数组
        list1[end], list1[0] = list1[0], list1[end]
        maxHeapify(list1, 0, end - 1)


# 最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
# start为当前需要调整最大堆的位置，end为调整边界
def maxHeapify(list1, start, end):
    root = start
    while True:
        child = root * 2 + 1  # 调整节点的子节点
        if child > end: break
        if child + 1 <= end and list1[child] < list1[child + 1]:
            child = child + 1  # 取较大的子节点
        if list1[root] < list1[child]:  # 较大的子节点成为父节点
            list1[root], list1[child] = list1[child], list1[root]  # 交换
            root = child
        else:
            break


if __name__ == '__main__':
    list1 = [random.randint(1, 999) for i in range(10000)]
    list11 = list1.copy()
    start1 = time.perf_counter()
    heapSort(list1)
    end1 = time.perf_counter()
    print("推排序       ", end1 - start1)

    start2 = time.perf_counter()
    list4 = sorted(list11)
    end2 = time.perf_counter()
    print("函数sorted排序", end2 - start2)
    print("排序结果", list1 == list4)
